package leetcode.lt100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class Solution_96 {

    public static void main(String[] args) {
        new Solution_96().numTrees(3);
    }

    public int numTrees(int n) {
        if (n == 0) {
            return 0;
        }
        return execute(1, n);
    }

    private int execute(int start, int end) {
        if (start > end) {
            return 1;
        }
        int res = 0;
        for (int i = start; i <= end; i++) {
            int left = execute(start, i - 1);
            int right = execute(i + 1, end);
            res += left * right;
        }
        return res;
    }

}